package Algorithm.DynamicPlanning;

/**
 * @Author cj
 * @Date 2022/11/9 20:53
 */
public class minCoins {

    // 暴力破解
    public int minCoins1(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return -1;
        }
        return process(arr, 0, aim);
    }

    private int process(int[] arr, int i, int rest) {
        // 考虑边界情况，没有面值可以考虑
        // 剩余钱为0，返回0张；剩余钱不是0，返回-1
        if (i == arr.length) {
            return rest == 0 ? 0 : -1;
        }
        int res = -1;
        for (int j = 0; j * arr[i] <= rest; j++) {
            int next = process(arr, i + 1, rest - j * arr[i]);
            if (next != -1) {
                res = res == -1 ? next + j : Math.min(next + j, res);
            }
        }
        return res;
    }

    // 动态规划：由暴力破解推出动态规划
    public int minCoins2(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return -1;
        }
        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];
        for (int col = 1; col <= aim; col++) {
            dp[N][col] = -1;
        }
        for (int i = N - 1; i >= 0; i--) {
            for (int rest = 0; rest <= aim; rest++) {
                // 初始先设置无效
                dp[i][rest] = -1;
                if (dp[i + 1][rest] != -1) { // 如果下面的值有效，先设置成下面的
                    dp[i][rest] = dp[i + 1][rest];
                }
                // 如果左边不越界且有效
                if (rest - arr[i] >= 0 && dp[i][rest - arr[i]] != -1) {
                    if (dp[i][rest] == -1) { // 如果之前的值无效，取左边的值
                        dp[i][rest] = dp[i][rest - arr[i]] + 1;
                    } else {
                        dp[i][rest] = Math.min(dp[i][rest],dp[i][rest - arr[i]] + 1);
                    }
                }
            }
        }
        return dp[0][aim];
    }

}
